#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2019 crane <crane@gosun>
#
# Distributed under terms of the MIT license.

"""
https://www.lintcode.com/problem/word-ladder/description


"""

class Solution:
    """
    @param: start: a string
    @param: end: a string
    @param: dict: a set of string
    @return: An integer
    """
    def ladderLength(self, start, end, dict):
        self.start = start
        self.end = end
        self.dict = set(dict)
        # return self.calc()
        return self.calc2()

    def calc(self):
        if self.start == self.end:
            return 1        # 仅仅self.start

        if self.is_neibor(self.start, self.end):
            return 2

        start_nexts = self.find_neighbor(self.start)
        end_nexts = self.find_neighbor(self.end)

        # 开始bfs广搜最短路径
        return self.bfs(start_nexts, end_nexts)

    def bfs(self, start_nexts, end_nexts):
        self.visited = set()
        queue = [(e, 2) for e in start_nexts]
        self.visited.union(queue)

        while queue:
            word, dis = queue.pop(0)        # pop开头
            if word in end_nexts:
                return dis + 1     # 2=[nei + self.end]

            # self.visited.add(word)

            neis = self.find_neighbor(word)
            for nei in neis:
                if nei in self.visited: continue
                self.visited.add(nei)
                queue.append( (nei, dis+1) )

        return -1

    def calc2(self):
        # double-direction bfs
        if self.start == self.end:
            return 1        # 仅仅self.start

        if self.is_neibor(self.start, self.end):
            return 2

        # start_nexts = self.find_neighbor(self.start)
        # # print('s nexts ', start_nexts)

        # end_nexts = self.find_neighbor(self.end)
        # print('e nexts ', end_nexts)

        # assert (self.start not in end_nexts) and (self.end not in self.start_nexts)

        # 开始bfs广搜最短路径
        # return self.double_bfs(start_nexts, end_nexts)
        return self.double_bfs()

    # def double_bfs(self, start_nexts, end_nexts):
    def double_bfs(self):
        cur_que_start = [self.start]
        # cur_que_end = [self.end]
        cur_que_end = self.find_neighbor(self.end, is_del=False)

        self.visited = set(cur_que_start)        # 用于 assert测试

        self.visited.union( cur_que_start )
        self.visited.union( cur_que_end )

        depth = 2
        while True:
            cur_que_start, is_match = self.get_next_que(cur_que_start, cur_que_end)
            depth += 1
            # print(depth)
            if is_match: return depth
            if not cur_que_start: return -1

            # if len(cur_que_start) < len(cur_que_end):
            #     cur_que_start, is_match = self.get_next_que(cur_que_start, cur_que_end)
            #     depth += 1
            #     print(depth)
            #     if is_match: return depth
            #     if not cur_que_start: return -1
            #     # self.visited.union(cur_que_start)
            # else:
            #     cur_que_end, is_match = self.get_next_que(cur_que_end, cur_que_start)
            #     depth += 1
            #     print(depth)
            #     if is_match: return depth
            #     if not cur_que_end: return -1
            #     # self.visited.union(cur_que_end)

    def get_next_que(self, cur_que, matched_que):
        # return matched
        set_cur = set(cur_que)
        set_match = set(matched_que)
        next_que = []
        for ele in cur_que:
            neis = self.find_neighbor(ele)
            for nei in neis:
                # if nei in cur_que: continue
                if nei in set_cur: continue         # 避免死循环
                if nei in set_match: return [], True
                # assert nei not in self.visited
                next_que.append(nei)

        return next_que, False

    def find_neighbor(self, word, is_del=True):
        # 优化
        res = set()

        if len(word) * 26 + 20 >= len(self.dict):
            for ele in self.dict:
                if self.is_neibor(word, ele):
                    res.add(ele)

            # if is_del:
            #     self.dict = self.dict.difference(res)
            # print('dict len ', len(self.dict))
        else:
            for idx in range(len(word)):
                for cv in range(ord('a'), ord('z')+1):
                    c = chr(cv)
                    if c == word[idx] : continue
                    s = word[0:idx] + c + word[idx+1:]
                    # print(word, s)
                    if s in self.dict:
                        # if is_del:
                        #     self.dict.remove(s)
                        if s not in self.visited:
                            res.add(s)
                            self.visited.add(s)

        return res

    def is_neibor(self, w1, w2):
        assert len(w1) == len(w2)

        diff = 0
        for idx in range(len(w1)):
            if w1[idx] != w2[idx]:
                diff += 1
                if diff > 1:
                    return False

        return diff == 1


    # def build_next_relation(self):
        # 没有必要, 用的时候计算, 也是可以的
        # 广度遍历, 不会重复, 所以也不会重复quer4

def test():
    s = Solution()

    lst = []
    assert s.ladderLength('a', 'a', lst) == 1

    lst = []
    assert s.ladderLength('a', 'c', lst) == 2

    lst = ['a', 'b', 'c']
    assert s.ladderLength('a', 'c', lst) == 2

    lst = ["hot","dot","dog","lot","log"]
    # print("ass ", s.ladderLength('hit', 'cog', lst) )
    assert s.ladderLength('hit', 'cog', lst) == 5

    lst = ['b']
    assert s.ladderLength('a', 'c', lst) == 2

    lst = ["ts","sc","ph","ca","jr","hf","to","if","ha","is","io","cf","ta"]
    assert s.ladderLength('ta', 'if', lst) == 4

    from q120_10 import lst120
    lst = lst120
    # print(len(lst))
    assert s.ladderLength('sand', 'acne', lst) == 11

    from q120_11 import lst120
    lst = lst120
    # print(len(lst))
    assert s.ladderLength('nanny', 'aloud', lst) == 20


def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
